package com.leetcode.linkedlist;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2019/10/8
 * @description:	142. 环形链表 II
 * B
 * 给定一个链表，返回链表开始入环的【第一个节点】。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 *
 * 说明：不允许修改给定的链表。
 *
 * 示例 1：
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：tail connects to node index 1
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 *
 * 示例 2：
 * 输入：head = [1,2], pos = 0
 * 输出：tail connects to node index 0
 * 解释：链表中有一个环，其尾部连接到第一个节点。
 *
 * 示例 3：
 * 输入：head = [1], pos = -1
 * 输出：no cycle
 * 解释：链表中没有环。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class DetectCycle142 {

	/**
	 * todo:【图文解析】返回链表开始入环的第一个结点	https://blog.csdn.net/qq_42351880/article/details/88960172
	 * todo:1 ms	93.13%
	 * @param head
	 * @return
	 */
	public ListNode detectCycle(ListNode head) {
		if (head==null){
			return null;
		}

		///1.求出相遇点
		ListNode fp=head;
		ListNode sp=head;
		///定义相遇节点
		ListNode meetNode=null;
		///boolean isCircle=false;
		while (fp!=null&&fp.next!=null){
			fp=fp.next.next;
			sp=sp.next;
			if (sp.equals(fp)){
				///确认环形链表,节省一个布尔值
				///isCircle=true;
				meetNode=sp;
				break;
			}
		}
		///如果无欢，返回 null
		if (meetNode==null){
			return null;
		}
		///2.有两个指针分别从 head 和 meetNode 出发
		ListNode p1=head;
		ListNode p2=meetNode;
		while (p1!=p2){
			p1=p1.next;
			p2=p2.next;
		}
		return p1;
	}


}
